121C - Lucky Permutation - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
using namespace std;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    k--;
    vector<int> ft(min(n+1, 20LL));
    ft[0] = 1;
    for(int i = 1; i < ft.size(); i++) {
        ft[i] = ft[i-1] * i;
    }
    if(ft.back() <= k) {
        cout << "-1\n";
        return 0;
    }
    vector<int> a;
    for(int i = ft.size()-1, j = k; i >= 1; i--) {
        a.push_back(j / ft[i-1]);
        j = j % ft[i-1];
    }
    vector<int> last;
    for(int i = 0; i < a.size(); i++) {
        last.push_back(n-a.size()+i+1);
    }
    for(int i = 0; i < last.size(); i++) {
        swap(last[i], last[i+a[i]]);
        sort(last.begin()+i+1, last.end());
    }
    function<int(int)> f = [&] (int i) {
        if(i < n - last.size() + 1) {
            return i;
        }
        else {
            return last[i - (n - last.size() + 1)];
        }
    };
    vector<int> lucky;
    for(int d = 1; d <= 9; d++) {
        for(int mask = 0; mask < (1 << d); mask++) {
            int num = 0;
            for(int i = 0; i < d; i++) {
                if(mask & (1 << i)) {
                    num = num * 10 + 7;
                }
                else {
                    num = num * 10 + 4;
                }
            }
            lucky.push_back(num);
        }
    }
    sort(lucky.begin(), lucky.end());
    int cnt = 0;
    for(int i : lucky) {
        if(i > n)
            break;
        int j = f(i);
        if(binary_search(lucky.begin(), lucky.end(), j)) {
            cnt++;
        }
    }
    cout << cnt << "\n";
}